package baseclass.l_string;

import java.util.Arrays;

/**
 * @date 2020/3/5 23:59
 */
public class Code03_KMP {

    public static int getIndexOf(String s1,String s2){
        if(s1 == null || s2 == null || s1.length() == 0 || s2.length() ==0)
            return -1;
        if(s1.length() < s2.length()) return -1;
        int i1 = 0;
        int i2 = 0;
        int[] next = getNext(s2.toCharArray());
        while (i1 < s1.length() && i2 < s2.length()){
            //继续比较下一位
            if(s1.charAt(i1) == s2.charAt(i2)){
                i1++;
                i2++;
            }else if(i2 == 0){// char[i1] != char[i2] && i2 == 0
                i1++;
            }else {
                i2 = next[i2];
            }
        }
        return i2 == s2.length() ? i1 - i2 : -1;
    }
    public static int[] getNext(char[]c){
        if(c== null || c.length == 0)return null;
        if(c.length == 1) return new int[]{-1};
        int[]next = new int[c.length];
        next[0] = -1;
        next[1] = 0;
        int cn = 0; //next
        int i = 2;
        while (i < c.length){
            if(c[i-1] == c[cn]){
                //那么i位置的长度是 i-1位置长度+1，也就是cn+1，并且cn往后挪动一位，方便复用
                next[i++] = ++cn;
                //否则cn就往前跳
            } else if (cn > 0) {
                cn = next[cn];
                //cn等于0，已经调到第1个位置了
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
    public static void main(String[] args) {

        String str1 = "aabaqsd";
        String str2 = "aqs";
        int[] next = getNext(str2.toCharArray());
        System.out.println(Arrays.toString(next));
        System.out.println(getIndexOf(str1,str2));

        //TODO  for test
    }

}
